\documentclass[a4paper, twocolumn]{article}

\usepackage[sc]{mathpazo} % Use the Palatino font
\usepackage[T1]{fontenc} % Use 8-bit encoding that has 256 glyphs
\linespread{1.05} % Line spacing - Palatino needs more space between lines
\usepackage{microtype} % Slightly tweak font spacing for aesthetics

\usepackage[english]{babel} % Language hyphenation and typographical rules

\usepackage[hmarginratio=1:1,top=32mm,left=20mm,right=20mm,columnsep=20pt]{geometry} % Document margins
\usepackage[hang, small,labelfont=bf,up,textfont=it,up]{caption} % Custom captions under/above floats in tables or figures
%\usepackage{booktabs} % Horizontal rules in tables

\usepackage{lettrine} % The lettrine is the first enlarged letter at the beginning of the text

\usepackage{enumitem} % Customized lists
\setlist[itemize]{noitemsep} % Make itemize lists more compact

\usepackage{abstract} % Allows abstract customization
\renewcommand{\abstractnamefont}{\normalfont\itshape\bfseries} % Set the "Abstract" text to bold
\renewcommand{\abstracttextfont}{\normalfont} % Set the abstract itself to small italic text

\usepackage{titlesec} % Allows customization of titles
\renewcommand\thesection{\Roman{section}} % Roman numerals for the sections
\renewcommand\thesubsection{\roman{subsection}} % roman numerals for subsections
\titleformat{\section}[block]{\large\scshape\centering}{\thesection.}{1em}{} % Change the look of the section titles
\titleformat{\subsection}[block]{\large}{\thesubsection.}{1em}{} % Change the look of the section titles

\usepackage{fancyhdr} % Headers and footers
\pagestyle{fancy} % All pages have headers and footers
\fancyhead{} % Blank out the default header
\fancyfoot{} % Blank out the default footer
\fancyhead[C]{\emph{Digital Image Processing 2016} Course Project Report}
\fancyfoot[RO,LE]{\thepage} % Custom footer text

\usepackage{titling} % Customizing the title section

\usepackage{hyperref} % For hyperlinks in the PDF
\hypersetup{hidelinks}

\usepackage{graphicx}

%----------------------------------------------------------------------------------------
%	TITLE SECTION
%----------------------------------------------------------------------------------------

\setlength{\droptitle}{-4\baselineskip} % Move the title up

\pretitle{\begin{center}\Huge\bfseries} % Article title formatting
	\posttitle{\end{center}} % Article title closing formatting
\title{Video Stabilization using Block Matching Algorithm} % Article title
\author{%
	\textsc{Liu Yang} \\[1ex] % Your name
	\normalsize Fudan University \\ % Your institution
	\normalsize \href{mailto:13307130167@fudan.edu.cn}{13307130167@fudan.edu.cn} % Your email address
}
\date{\today} % Leave empty to omit a date
\renewcommand{\maketitlehookd}{%
\begin{abstract}
%	\noindent
	\textbf{
		This report presents a video stabilization method based on block matching algorithm. It discusses a typical block matching algorithm -- EBMA, and compares EBMA with some faster block matching algorithm, along with video stabilization implement result in MATLAB code.
	}
\end{abstract}
}
%----------------------------------------------------------------------------------------

\begin{document}
	
	% Print the title
	\maketitle
	
	%----------------------------------------------------------------------------------------
%		ARTICLE CONTENTS
	%----------------------------------------------------------------------------------------
	\section{Introduction}
	
	\lettrine[nindent=0em,lines=3]{V} ideo stabilization is a key problem in producing high quality video sequence, especially when we are in self-media age and much more videos are shot with smart phones, which means video stabilization is in great demand. \\
	Typically, there are three steps in video stabilization workflow: 
	
	\begin{itemize}
		\item motion estimation
		\item shaking recognition
		\item motion compensation
	\end{itemize}
	\noindent
	Among all three steps, the most computationally expensive and resource consumed one is motion estimation. Some mature models are discussed in \cite{vpc}: based on optical flow, based on pixel, based on block, based on mesh, etc. \\
	This report and video stabilization implement focus on block-based algorithm, starting with naive and slow EBMA, to some other improved and faster algorithm. The algorithms that have been implemented are Exhaustive Block Matching Algorithm (EBMA), 2-D Log Search Method (a.k.a Diamond Search, DS), Three-Step Search Method (TSS). Multi-Resolution Motion Estimation with Hierarchical Block Matching Algorithm (HBMA) is also introduced. Section II explains how these algorithms work. Section III makes a comparison between the first three algorithms. Section IV presents a way to recognize shaking and shows the video stabilization result with motion compensation.
	
	%------------------------------------------------
	
	\section{Block Matching Algorithm}
	Considering motion estimation between two given frames, $ \psi(x,y, t_{1}) $ and $ \psi(x,y,t_{2}) $, we define motion vector (MV) at \textbf{x} between time $ t_{1} $ and $ t_{2} $ is the displacement of this point from $ t_{1} $ to $ t_{2} $. We will call the frame at time $ t_{1} $ the anchor frame, and the frame at time $ t_{2} $ the tracked frame. The anchor frame can be either before or after the tracked frame, as illustrated in Figure \ref{fig:backwards}. It is forward motion estimation when $ t_{1} < t_{2} $ while backward motion estimation when $ t_{1} > t_{2} $. We use $ \psi_{1}(\textbf{x}) $ to denote anchor frame and $ \psi_{2}(\textbf{x}) $ to denote tracked frame. \\
	In this report and the implement, we use backward motion estimation.
	\begin{figure}[h]
	\centering
	\includegraphics[width=1\linewidth]{backwards}
	\caption{Forward and backward motion estimation}
	\label{fig:backwards}
	\end{figure}

	\noindent	
	The idea behind motion estimation is to find the most similar part of two continuous frame, use the displacement of this two matched part as the motion vector.  Block Matching Algorithm (BMA) is a collection of block-based motion estimation algorithms.  BMA divide the whole video frame into non-overlapping small regions, usually called blocks, and assume that the motion within each block can be characterized by a simple parametric model, e.g., constant, affine or bilinear. If the block is sufficiently small, then we can get a quite accurate motion estimation. \\
	In the discussion below, $\Lambda$ will denote the whole video frame. And we divide a frame into $ M $ blocks, we use $ \beta_{ij} $ to represent the \textit{i}-th row, \textit{j}-th column block. So the block partition should satisfy: 
	\begin{displaymath}
		\cup  \beta_{ij} = \Lambda, \textrm{and} \quad \beta_{ij}  \cap \beta_{i'j'} = \emptyset, i \ne i', j \ne j' .
	\end{displaymath}
	In this report, the block is always square shape. And we assume the motion in each block is constant, i.e., the entire block is in same motion, which is called \textit{block-wise translational model}. \\
	The task of BMA is to find a single motion vector for each block. Given a block $ \beta $ in the anchor frame, motion estimation is to find a most matched block $ \beta' $ in the tracked frame so that the error between this two blocks is minimized. And the displacement vector \textbf{d} between this two blocks is the MV of the block in tracked frame. Since we simply adapt the block-wise translational model, estimated block can be represented as $ \beta_{es} = \beta_{an} + \textbf{d} $. So the error can be written as: 
	\begin{displaymath}
		\textit{E}(\textbf{d}_{m}, \forall 1 \leq m \leq M) = \sum_{m} \sum_{\beta \in \beta_{ij}} 
		| \psi_{2}(\beta + \textbf{d}_{m}) - \psi_{1}(\beta) | ^ {p}
	\end{displaymath}
	where $ \psi $ represents the gray value, $ \psi_{2} $ for tracked frame, $ \psi_{1} $ for anchor frame.\\
	Because all blocks in anchor frame is estimated independently, so the error minimizing problem is to minimize estimation error for each block, which is: 
	\begin{equation}
		\label{eq:error}
		\textit{E}_{m}(\textbf{d}_{m}) = \sum_{\beta \in \beta_{ij}} | \psi_{2}(\beta + \textbf{d}_{m}) - \psi_{1}(\beta) | ^{p}
	\end{equation}
	To reduce computational load, the Mean Absolute Difference (MAD) error ( $ p = 1 $) is used in this report and the implement.
	\subsection{Exhaustive Block Matching Algorithm}
	Exhaustive Block Matching Algorithm (EBMA) is also called Full Search. It is the simplest but most computational expensive block matching algorithm of all.\\
	For a given block $ \beta $ in the anchor frame, EBMA searches surrounding area of $ \beta $, compares $ \beta $ with all candidate blocks $ \beta_{can} $ in the tracked frame and find best matched candidate block $ \beta' $ with minimum error. Then the displacement between anchor block $ \beta $ and best matched block $ \beta' $ is the estimated motion vector. \\
	In EBMA, search area can be parameterized by $ R_x $ pixels horizontally and $ R_y $ pixels vertically. Both $ R_x $ and $ R_y $ is symmetric with respect to the center of the anchor block $ \beta $. Usually the shaking is random both horizontally and vertically, so search area is a square area with $ R  = R_x = R_y $. \\
	EBMA can be illustrated in Figure \ref{fig:EBMA}. \\
	\begin{figure}[h]
	\centering
	\includegraphics[width=1\linewidth]{EBMA}
	\caption[EBMA figure]{The search procedure of EBMA for one anchor block}
	\label{fig:EBMA}
	\end{figure}
	
	\noindent
	For EBMA, the estimation accuracy can be specified by search step size, which is the distance between two nearby candidate blocks in the horizontal or vertical direction. 
	In this report and the implement, the same step size is used in both directions. In most case, step size is one pixel and is called \textit{integer-pel accuracy search}. On the other hand, for those low resolution frame, a more accurate motion estimation is needed. So in this case, we will use fractional-pel accuracy search. But there exists a problem that there may not be corresponding candidate points in the tracked frame for certain sample anchor points. To realize a step size of $ 1/K $ pixel search, the tracked frame firstly needs to be resized by factor $ K $. Typically the $ K = 2 $, which is know as \textit{half-pel accuracy search}. Half-pel accuracy search is shown in Figure \ref{fig:half-EBMA}.
	\begin{figure}[h]
	\centering
	\includegraphics[width=1\linewidth]{half-EBMA}
	\caption[half EBMA]{Half-pel accuracy block matching. Filled circles are samples existing in the original tracked frame, open circles are samples to be interpolated for calculating the matching error.}
	\label{fig:half-EBMA}
	\end{figure}
	
	\noindent
	Although EBMA can get a global optimal motion estimation and with half-pel accuracy search it can get more accurate, one obvious disadvantage of EBMA is that it requires intense computation when goes on with full search regardless of the possibility of candidate block to be the most matched block. \\
	Because of the computation problem, several faster algorithms have been developed to get a trade-off between the estimation accuracy and computation efficiency.
	
	\subsection{2-D Log Search Method}
	2-D Log Search Method is also known as Diamond Search. It is illustrated in Figure \ref{fig:ds}
	
	\begin{figure}[h]
	\centering
	\includegraphics[width=0.9\linewidth]{ds}
	\caption{2-D Log Search Method. Search points start with black circles, end with gray circles.}
	\label{fig:ds}
	\end{figure}

	\noindent
	It starts from the position corresponding to zero-displacement of the anchor block. In each step, nine nearby points within diamond shape will be tested to get a best matched point. Then the center of search area will move to the best matched point resulting from the previous step and repeat the step. In 2-D log search method, the search step size, also represents the radius of the search diamond shape, is reduced by one if the best matched point is the center point of the diamond, or on the border of the search area. Otherwise, the step size will remain same in next search step.
	The final step is reached when the step size reaches 1 pixel range. Usually the initial step size is set to be half of the max search range. \\
	As the fact that the number of steps and the total number of search points depends on the actual motion vectors, there is no limit to the number of 2-D log search steps, so it could find global minimum accurately while the computation expense goes down quickly.
	
	\subsection{Three-Step Search Method}
	As illustrated in Figure \ref{fig:tss}, the search starts with a step size equal to or slightly larger than half of the maximum search range. In each step, nine search points, which are in a square shape around the center of the previous search step, are compared. The step size is reduced by half after each step, and the search ends with step size reaching 1 pixel range. At each new step, the search center is moved to the best matched point resulting from the previous step.
	
	\begin{figure}[h]
	\centering
	\includegraphics[width=0.9\linewidth]{tss}
	\caption{Three-Step Search Method. Search points start with black circle, end with black square.}
	\label{fig:tss}
	\end{figure}
	
	\noindent
	Let $ R_{0} $ represent the initial search step size, there are at most $ L = \lfloor   \log_{2}{R_{0} + 1} \rfloor $ search step. At each search step, eight points are searched, except in the very first nine points searched. So the total number of search points is $ 8L + 1 $. For example, for a search range of $ R = 32 $, with EBMA, the total number of search points is $ (2*R+1)^2 = (2*32+1)^2 = 4225 $, whereas with three-step search method, the number is 41, ($ L = \lfloor   \log_{2}{R_{0} + 1} \rfloor = \lfloor   \log_{2}{\frac{32}{2} + 1} \rfloor = 5, 8*L+1 = 41$ ). Three-step search method is over 100 times efficient than EBMA.
	
	\subsection{Hierarchical Block Matching Algorithm}
	Among above motion estimation methods, there two major difficulties when obtaining the correct solution:
	\begin{enumerate}
		\item the minimization function usually has many local minimum and it is not easy to reach the global minimum.
		\item the expense of computation is very high.
	\end{enumerate}
	To cope with above two problems, hierarchical block matching algorithm (HBMA) with multi-resolution approach is developed. It searches the optimal solution in successively finer resolutions, as illustrated in Figure \ref{fig:hbma}.
	
	\begin{figure}[h]
	\centering
	\includegraphics[width=1\linewidth]{hbma}
	\caption{3-level hierarchical block matching algorithm}
	\label{fig:hbma}
	\end{figure}

	\noindent
	First, we get pyramid-like representations of anchor frame and tracked frame. Each level is a resized frame as  a reduced resolution representation, where bottom level is the original one. The higher the level is, the lower its resolution is. Typical resolution reduction factor between two successive levels is 2, both horizontally and vertically. Then the motion vectors between corresponding levels of the two pyramids is estimated, starting from the top coarsest level and processing to the lower finer level repeatedly.\\
	Here we assume the same block size is used at different levels, so that the number of blocks is reduced by half in each dimension as well. Let the motion vector for block $ (i, j) $ as level $ l $ be denoted by $ \textbf{d}_{l, i, j} $. Starting from top level, we first find the motion vectors for all blocks in this level. At each lower level $ l > 1 $, for each block, its initial motion vector $ \widetilde{\textbf{d}}_{l, i, j} $ is interpolated from a corresponding block in level $ l - 1 $ by 
	\begin{displaymath}
		\widetilde{\textbf{d}}_{l, i, j} = 2*\textbf{d}_{l-1, \lfloor i/2 \rfloor, \lfloor j/2 \rfloor}
	\end{displaymath}
	Then within the search area, we search and get a correction vector $ \textbf{q}_{l, i, j} $, then make the correction to get the final estimated motion vector
	\begin{displaymath}
		\textbf{d}_{l, i, j} = \widetilde{\textbf{d}}_{l, i, j} + \textbf{q}_{l, i, j}
	\end{displaymath}
	We could notice that using a block with $ N $ size at level $ l $ corresponds to a block size of $ 2^{L-l} * N$ at the full resolution. Therefore, by using the same block size, search range and step size at different levels, we actually use a larger block size, a larger search range and a larger step size in the beginning of the search, and then gradually half-reduce these three parameters in successive level steps.\\
	The benefit of HBMA is that by first searching the solution in a coarse resolution, one can usually obtain a solution that is close to the true motion vector. In addition, by limiting the search area to a small neighborhood of the solution obtained in the previous resolution, the total number of searches can be reduced, compared to those required by directly searching in the finest resolution over a large range.
	
	%------------------------------------------------
	
	\section{Algorithm Comparison}
	This comparison part mainly focuses on three BMA: EBMA, 2-D Log Search Method and Three-Step Search Method.
	\subsection{Computation Expense}
	As we already discussed in section II, EBMA is a most computation expensive algorithm, while 2-D log search method and three-step search method could drop the expense greatly. \\
	 As shown in Figure \ref{fig:block}, in our comparison experiment, video has 32 frames, block is divided as $ 16*16 \textit{ } pel $ square and search area is set to be $ 7 \textit{ } pel $.\\
	\begin{figure}[hb]
	\centering
	\includegraphics[width=1\linewidth]{block}
	\caption{EBMA search block with 16 pel size and 7 pel range.}
	\label{fig:block}
	\end{figure}
	
	\noindent
	Search points for a certain anchor block in EBMA is fixed once search range is fixed, in this case is $ (2*R+1)^2 = (2*7+1)^2=255 $ searches per block.\\
	Since in each search of BMA, it is necessary to compute on the entire block to get MAD error value, we only need to compare the average search times per block of these three algorithms. And because the average search times of EBMA is one magnitude larger than the other two, we do not plot it in the result figure. So the computation expense comparison between 2-D log search method and three-step search method is plot in Figure \ref{fig:expense}.
	\begin{figure}[h]
	\centering
	\includegraphics[width=1\linewidth]{expense}
	\caption{Computation expense comparison between TSS and 2DLS}
	\label{fig:expense}
	\end{figure}
	
	\noindent
	In Figure \ref{fig:expense}, we can see that 2-D log search method and three-step search method is actually one magnitude faster than EBMA. Meanwhile 2-D log search method is slightly faster than three-step search method, which means our experiment video undergoes small shaking.
	
	\subsection{Accuracy}
	In equation \ref{eq:error}, when $ q = 2 $, then equation \ref{eq:error} goes to be Mean Square Error (MSE), which is also an error evaluation method. \\
	Instead of the MSE, the \textit{peak signal to noise ratio} (PSNR) in decibel (dB) is more often used as a quality measure in video coding. The PSNR is defined as 
	\begin{equation}
		PSNR = 10 \log_{10} \frac{\psi_{max}^2}{MSE}
	\end{equation}
	where $ \psi_{max} $ is the peak (maximum) intensity value of the anchor frame.\\
	PSNR value is used in our algorithm accuracy comparison. PSNR evaluates the quality of compensated frame resulting from estimated motion vectors. \\
	In Figure \ref{fig:psnr} , we plot PSNR values of these three algorithms. 
	\begin{figure}[h]
	\centering
	\includegraphics[width=1\linewidth]{psnr}
	\caption{Accuracy comparison between EBMA, TSS and 2DLS}
	\label{fig:psnr}
	\end{figure}

	\noindent
	In Figure \ref{fig:psnr}, we can see EBMA gets the highest PSNR value, which means it gets the most accurate compensated result. 2-D log search method gets a result close to the best one, which is caused by the unlimited search steps by this algorithm to able to get the global optimal motion vector. Three-step search method gets the worst compensated results in all frames because it only allows limited search steps, usually 3$\sim$4 times, and easily to get a local optimal motion vector.\\
	So although EBMA is most computationally expensive and resource consumed, it could get best result. While three-step search method drop the search times dramatically, it might get a not so good result. 2-D log search method is a good trade-off between computational expense and accuracy.
	
	%------------------------------------------------
	
	\section{Experiment}
	\subsection{Block Motion Vectors}
	With the implemented MATLAB code for EBMA, 2-D log search method, three-step search method and HBMA, we could get the following results showing the estimated motion vectors. We use 'red-cyan' color channel to distinguish anchor frame and tracked frame, red represents tracked frame and cyan represents anchor frame.
	\begin{enumerate}
		\item motion vectors from EBMA is in Figure \ref{fig:ebma-mv}
		\item motion vectors from 2-D Log Search Method is in Figure \ref{fig:2dls-mv}
		\item motion vectors from Three-Step Search Method is in Figure \ref{fig:tss-mv}
	\end{enumerate}
	\begin{figure}[h]
	\centering
	\includegraphics[width=1\linewidth]{ebma-mv}
	\caption{Motion vector resulting from EBMA}
	\label{fig:ebma-mv}
	\end{figure}

	\begin{figure}[h]
	\centering
	\includegraphics[width=1\linewidth]{2dls-mv}
	\caption{Motion vector resulting from 2-D log search method}
	\label{fig:2dls-mv}
	\end{figure}

	\begin{figure}[h]
	\centering
	\includegraphics[width=1\linewidth]{tss-mv}
	\caption{Motion vector resulting from three-step search method}
	\label{fig:tss-mv}
	\end{figure}

	\subsection{Global Motion Vector}
	With the estimated motion vector of each block done by presented BMA, we could carry on with shaking recognition part.
	From block motion vectors of a frame, we can evaluate a vector identifying unwanted movements. This vector summarizes the motion of the frame and is called Global Motion Vector (GMV).\\
	One way to get GMV is simply letting the most frequent vector presented in the block motion vectors be the GMV. This way assumes that most part of the frame undergoes the exactly same displacement. \\
	But the drawback of BMA is that not all block motion vectors are reliable. For example, considering Figure \ref{fig:mad_diff} below, a homogeneous block in a homogeneous area can give a wrong motion vector as a poor match is found. In Figure \ref{fig:mad_diff}, block MAD is calculated by
	\begin{equation}
		MAD = \frac{1}{N^2} \sum_{j=0}^{N-1} \sum_{i=0}^{N-1} | Y_{i,j} - \bar{Y} |
	\end{equation}
	where $ \bar{Y} $ is the average gray value in the block. \\
	So the lower the MAD of block $ \beta $ is, the more likely $ \beta $ is homogeneous.
	\begin{figure}[h]
	\centering
	\includegraphics[width=1\linewidth]{mad_diff}
	\caption{Different MAD to present homogeneousness}
	\label{fig:mad_diff}
	\end{figure}
	
	\noindent
	With simple counting method to get GMV, a number of unreliable motion vectors might be used and will lead to wrong GMV result.\\
	An improved way to get GMV is weighted counting. Different weights for the motion vector counting are considered. Homogeneous blocks will have a low weight while block with high MAD value will have a higher weight. In this way a most reliable block will be counted with more strength than a normal block.\\
	Weight values are assigned considering that higher the MAD value is, the bigger must be the weight associated with its motion vector. In this report and its implement, we use a weight table \ref{tb:weight}.
	
	\begin{table}[h]
		\caption{Weights for BMV}
		\label{tb:weight}
		\centering
		\begin{tabular}{|c | c|}
			\hline
			\textbf{MAD} & \textbf{Weight} \\ 
			\hline
			MAD < 5 & 0 \\ 
			\hline
			5 $\leq$ MAD < 40 & 1 \\ 
			\hline
			40 $\leq$ MAD < 60 & 2 \\ 
			\hline
			60 $\leq$ MAD < 80 & 4 \\ 
			\hline
			80 $\leq$ MAD < 100 & 8 \\ 
			\hline
			MAD $\geq$100 & 16 \\
			\hline
		\end{tabular}
	\end{table} 	
	
	\noindent
	Now the most weighted motion vector will be chosen as the global motion vector.
	
	\subsection{Motion Compensation}
	The above global motion vector of tracked frame corresponds to the anchor frame. To have a stabilization of the whole series of frames, the compensation must be done corresponding to a common reference frame, which in our case is the first frame of the video. So each tracked frame's global motion vector will accumulate to get the absolute global motion vector. Absolute GMV is considered as the vector referred to the absolute coordinate system. So the compensation will be done relying on this absolute GMV. \\
	The final big problem in motion compensation is to distinguish between jiggling and panning. Jiggling is the shaking that lowers the video quality and need to be stabilized.
	For most case, jiggling is in small scale and in random direction. Panning is intended movement by the video shooter and we want to keep panning movement in stabilized video. Unlike jiggling, panning is in coherent direction and in a bigger movement than jiggling. \\
	In \cite{abmvf}, it uses absolute GMV and set a hard threshold to discriminate jiggling from panning.\\
	Instead, in this report and its implement, we use another way to distinguish between jiggling and panning. When jiggling appears, the frame is changed by a little, which means the MAD values of anchor frame and tracked frame is almost the same. While in the panning, most of the frame will be moved out by a certain amount of pixels, leading to a quite large change in the MAD values of anchor frame and tracked frame. So we use the following judgment (Figure \ref{fig:judgment}) to judge whether the frame undergoes jiggling or panning. Here when encountering panning, we reset absolute GMV to switch to a new video context and consider the frame after panning as a new common reference frame.
	 
	 \begin{figure}[h]
	\centering
	\includegraphics[width=0.7\linewidth]{judgment}
	\caption{Jiggling and Panning Judgment}
	\label{fig:judgment}
	\end{figure}
	
	\subsection{Final Result}
	Here lists some captures of the stabilized video \ref{fig:f1}, \ref{fig:f2}, \ref{fig:f3}. Left is the original and right is the compensated.
	
	\begin{figure}[h]
	\centering
	\includegraphics[width=1\linewidth]{f1}
	\caption{Original frame and compensated frame at the beginning of video}
	\label{fig:f1}
	\end{figure}
	\begin{figure}[h]
	\centering
	\includegraphics[width=1\linewidth]{f2}
	\caption{Original frame and compensated frame in the middle of the video}
	\label{fig:f2}
	\end{figure}
	\begin{figure}[h]
	\centering
	\includegraphics[width=1\linewidth]{f3}
	\caption{Original frame and compensated frame at the end of the video}
	\label{fig:f3}
	\end{figure}
	
	\noindent
	The final stabilized video is available here: \href{https://youtu.be/YMaCjQ8-WY0}{Youtube} or \href{http://pan.baidu.com/s/1bGrkvW}{BaiduYun}: 

	%------------------------------------------------
	
	\section{Conclusion}
	Block Matching Algorithm is a widely used algorithm in video stabilization. Among three BMAs that we compare, EBMA is the most computationally expensive but most accurate one. Three-Step Search Method requires much less computational resource but decreases the quality of estimated motion vectors. 2-D Log Search Method gains a balance between computational expense and accuracy. HBMA develops a new idea about search blocks. \\
	Global motion vector is generated by counting block motion vectors with different weights. Discrimination between jiggling and panning is considered by applying MAD value comparison. \\
	One obvious drawback of block matching algorithm in video stabilization is that it could hardly stabilize rotation in the frame.
	
	\section{Acknowledgement}
	MATLAB code used to generate the comparison results in section III is provided by \href{http://www.mathworks.com/matlabcentral/profile/authors/870112-aroh-barjatya}{\textit{Aroh Barjatya}} on \href{http://www.mathworks.com/matlabcentral/fileexchange/8761-block-matching-algorithms-for-motion-estimation}{\textit{MathWorks Community}}.

	%----------------------------------------------------------------------------------------
	%	REFERENCE LIST
	%----------------------------------------------------------------------------------------
	
	\begin{thebibliography}{99} % Bibliography - this is intentionally simple in this template
		
		\bibitem{vpc}
		Wang Y, Ostermann J, Zhang Y Q. 
		\newblock {\em Video processing and communications[M]. Chap. 6: Two Dimensional Motion Estimation.}  
		\newblock Upper Saddle River: Prentice Hall, 2002.
		
		\bibitem{abmvf}
		Vella F, Castorina A, Mancuso M, et al. 
		\newblock {\em Digital image stabilization by adaptive block motion vectors filtering[J].}
		\newblock IEEE Transactions on Consumer Electronics, 2002, 48(3): 796-801.
		
		\bibitem{hbma}
		Bierling M. 
		\newblock {\em Displacement estimation by hierarchical blockmatching[C].}
		\newblock Visual Communications and Image Processing'88: Third in a Series. International Society for Optics and Photonics, 1988: 942-953.
		
		\bibitem{cr}
		Engelsberg A, Schmidt G. 
		\newblock {\em A comparative review of digital image stabilising algorithms for mobile video communications[J].}
		\newblock Consumer Electronics, IEEE Transactions on, 1999, 45(3): 591-597.
		
	\end{thebibliography}
	
	%----------------------------------------------------------------------------------------
	
\end{document}
